#pragma once
#ifndef _PARSOLVER_H
#define _PARSOLVER_H

#include <stack>

#include "move.h"
#include "stackrecord.h"
#include "solution.h"

//////////////////////////////////////////////////////////////////////////
// trida resici problem pomoci mpi
class ParSolver
{
	InstanceI* instance;
	mpi::environment* envp;
	mpi::communicator* worldp;
	StackRecord::boardLayout_t solutionLayout;
	ParStack openNodes;
	Solution tempBest;
	size_t stateCounter;

	struct InstanceCache {
		typedef const unsigned cache_t;
		cache_t n,k,q;
		InstanceCache(cache_t _n, cache_t _k, cache_t _q)
			: n(_n), k(_k), q(_q)
		{}
	};

	const InstanceCache icache;

public:

	//////////////////////////////////////////////////////////////////////////
	ParSolver(InstanceI* _ip, mpi::environment* _envp, mpi::communicator* _worldp)
		: instance(_ip), envp(_envp), worldp(_worldp),
		icache(instance->n(), instance->k(), instance->q())
	{
		solutionLayout = StackRecord::boardLayout_t(icache.n * icache.n);
	}

	//////////////////////////////////////////////////////////////////////////
	virtual Solution solve()
	{
		commonInit();
		
		//Main node
		if (worldp->rank() == 0)
		{
			StackRecord::boardLayout_t start = createLayout(*instance);
			openNodes.push(StackRecord(start)); //s prazdnou historii
			initialWorkSend();
		}
		else //other nodes
		{
			receiveWork();
		}

		runDistroSolve();

		return tempBest;
	}

	//////////////////////////////////////////////////////////////////////////
	virtual ~ParSolver(){}

private:

	enum MessageType
	{
		WORKUNIT, ENDTOKEN
	};

	enum ProcessState
	{
		START, COMPUTE
	};

	void commonInit()
	{
		createSolLay();
		stateCounter = 0;
	}

	void runDistroSolve()
	{
		ProcessState state = START;

		while(true) //inf. loop
		{
			switch(state)
			{
			case START:
				{
					
					state=COMPUTE;
					break;
				}
			case COMPUTE:
				{
					break;
				}

			default:
				{
					std::cerr << "Neznamy stav." << std::endl;
					throw "Neznamy stav.";
				}
			} //switch
		} //inf loop
	} //runDistroSolve

	//////////////////////////////////////////////////////////////////////////
	void initialWorkSend()
	{
		utils::log("initialWorkSend begins");
		unsigned nodesToGo = worldp->size()-1; //pocet uzlu, ktere potrebuji jeste dostat praci
		std::vector<ParStack::workUnit_t> units;
		
		while (!openNodes.empty() && nodesToGo>0)
		{	
			processTopSolution();
			expandTop();
			units = openNodes.divide(nodesToGo, icache.q-2);

			nodesToGo-=units.size();
		}
		
		
		
		
		
	}


	//////////////////////////////////////////////////////////////////////////
	//Vytvori rozlozeni sachovnice odpovidajici hledanemu reseni.
	void createSolLay()
	{
		unsigned cnt = icache.k;
		unsigned y = 0, x = 0; //zacnu nahore vlevo
		unsigned zarazka = icache.n;
		while (cnt > 0)
		{
			unsigned index = utils::coordsToIndex(x,y,icache.n);
			solutionLayout.setAt(index,true);
			x++;
			if (x>=zarazka)
			{
				x = 0; //zpet na zacatek radku
				y++; //po radcich dolu
				zarazka--;
			}
			cnt--;
		}
	}

	//////////////////////////////////////////////////////////////////////////
	// Otestuje, zda je na vrcholu zasobniku reseni a podle toho jej dale zpracuje
	void processStackTop()
	{
		if(isTopSolution())
		{ //na vrcholu zasobniku je reseni!
			StackRecord top = openNodes.top();
			openNodes.pop(); //z reseni uz nebude lepsi.. leda bychom meli zaporne penalizace (coz nemame)
			if (tempBest.penaltySum > top.totalPenalty)
			{ //nasli jsme lepsi reseni!
				std::cout << "Velikost zasobniku: "<< openNodes.size() << "\n";
				std::cout << "Pocet prohledanych stavu: "<< this->stateCounter << "\n";
				std::cout << "SOLUTION:\n" << top << std::endl;
				tempBest = Solution(top.movesHistory, top.totalPenalty);
			}
		}
		//pokud neni reseni, nic se nestane.
	}

	//////////////////////////////////////////////////////////////////////////
	// testuje, zda je na vrcholu zasobniku reseni
	bool isTopSolution()
	{
		return openNodes.top().boardLayout == solutionLayout;
	}

	//////////////////////////////////////////////////////////////////////////
	// Vybere z vrcholu stav a na zasobnik umisti jeho naslendiky.
	void expandTop()
	{
		if (openNodes.empty())
		{
			return;
		}
		StackRecord actual = openNodes.top();
		openNodes.pop();
		this->stateCounter++;
		//max hloubka:
		if (actual.depth == icache.q)
		{
			return;
		}
		if (actual.totalPenalty>=tempBest.penaltySum)
		{ //z tohoto uzlu uz nebude lepsi reseni nez jaky jsem uz nasel. oriznout..
			return;
		}
		//uchovam si souradnice na vychozi pozici posledne tazeneho kone:
		utils::coords_t * origCp;
		if (!actual.movesHistory.empty()) //pozor pri prvnim tahu, zadna historie..
		{
			origCp = &(actual.movesHistory.back().origCoords);
		}
		//Generovani vsech tahu:
		for (unsigned i = 0; i<actual.boardLayout.size(); ++i)
		{
			if (!actual.boardLayout[i])
			{
				continue;
			}
			for (unsigned j = 1; j<=8; ++j)
			{
				Move m = Move(utils::indexToCoords(i,icache.n), (Direction) j);
				if (m.targetCoords == *origCp)
				{
					continue;
				}
				StackRecord::boardLayout_t newL = move(actual.boardLayout, m);
				if (newL == actual.boardLayout)
				{	//Pokud je tah neplatny, vratilo mi to nezmenenou konfiguraci
					continue; 
				}
				unsigned pen = instance->getPenalty(m.targetCoords);
				openNodes.push(StackRecord(newL,actual,m,pen));
			}
		}
	} //end expandTop

	//////////////////////////////////////////////////////////////////////////
	// Funkce, ktera aplikuje samotny tah na danou desku.
	// Nezda se to jako uplne dobry navrh (objektove), ale funguje..
	//
	// returns new layout or the SAME layout (as on input), if the move would be invalid.
	StackRecord::boardLayout_t move(const StackRecord::boardLayout_t &_inLay, const Move& _m)
	{
		utils::coords_t new_coor = _m.targetCoords;
		unsigned new_index;
		if(	new_coor.first>=icache.n || //kontrola souradnic
			new_coor.second>=icache.n ||
			_inLay[(new_index = utils::coordsToIndex(new_coor, icache.n))] //test cilove pozice, jestli je volna
		)
		{
			return _inLay; //v pripade ze tento tah neni platny, vratim puvodni rozlozeni
		}
		StackRecord::boardLayout_t new_lay = _inLay;
		new_lay.setAt(utils::coordsToIndex(_m.origCoords, icache.n), false);
		new_lay.setAt(new_index, true);

		return new_lay;
	}

	//////////////////////////////////////////////////////////////////////////
	//Metoda pro vytvoreni bitmapy sachovnice pro dane zadani.
	static StackRecord::boardLayout_t createLayout(Instance &_inst)
	{
		StackRecord::boardLayout_t lay(_inst.n() * _inst.n()); //velikost n*n !!
		for (unsigned i = 0; i < _inst.getHorses().size(); ++i)
		{
			unsigned x = _inst.getHorses()[i].x;
			unsigned y = _inst.getHorses()[i].y;
			unsigned index = utils::coordsToIndex( x, y, _inst.n());
			lay.setAt(index, true);
		}
		return lay;
	}

}; //end ParSolver

#endif //_PARSOLVER_H

